package generic.genetic.chromosome;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;


public class PermutationChromosome extends Chromosome {

	protected int[] permutation;
	
	public PermutationChromosome(int nGenes) {
		this.nGenes = nGenes;
		permutation = new int[nGenes];
	}
	
	public PermutationChromosome(PermutationChromosome c) {
		this.nGenes = c.getnGenes();
		this.permutation = c.getPermutation();
	}

	@Override
	public void randomInit(int init_type) {
		Random r = new Random();
		ArrayList<Integer> ints = new ArrayList<>();
		int pos;
		for (int i=0;i<nGenes;i++) ints.add(i);
		for (int i=0;i<nGenes;i++){
			pos = r.nextInt(ints.size());
			permutation[i] = ints.get(pos);
			ints.remove(pos);
		}
	}

	public void cross(int type, Chromosome c){
		cross(type,(PermutationChromosome) c);
	}
	
	@Override
	public boolean mutation(int type, double mutation_rate) {
		
		Random r = new Random();
		if (r.nextFloat() >= mutation_rate) return false;
		
		int n = 3;
		int[] p = randomElems(2);
		int[] rs = randomElems(3);
		
		switch (type){
		case 0: mutation_inversion(p[0],p[1]); break;
		case 1: mutation_exchange(p[0],p[1]); break;
		case 2: mutation_insertion(n); break;
		case 3: mutation_heuristic(rs); break;
		case 4: mutation_shuffle(); break;
		case 5: mutation_barrel_shifter(n); break;
		}
		return true;
	}

	public void cross(int type, PermutationChromosome c){
		
		int[] p = randomElems(2);
		
		switch (type){
		case 0: this.cross_PMX(c,p[0],p[1]); break;
		case 1: this.cross_OX(c,p[0],p[1]); break;
		case 2: this.cross_OX_pos_priority(c); break;
		case 3: this.cross_OX_ord_priority(c); break;
		case 4: this.cross_CX(c); break;
		case 5: this.cross_ERX(c); break;
		case 6: this.cross_Ordinal(c,p[1]); break;
		case 7: this.cross_mult_insertion(c,p[0],p[1]); break;
		}
	}
	
	
	/**
	 * Crossover Method : Partially Matched Crossover [PMX] (Deterministic)
	 * @param c Second parent
	 */
	private void cross_PMX(PermutationChromosome c, int p1, int p2) {
		
		if (p2 < p1){ int tmp = p2; p2 = p1; p1 = tmp; }
				
		int c1[] = new int[nGenes];
		int c2[] = new int[nGenes];
		int[] perm2 = c.getPermutation();
		
		for (int i=0;i<nGenes;i++){
			c1[i] = -1;
			c2[i] = -1;
		}
		
		for (int i=p1;i<p2;i++){
			c1[i] = perm2[i];
			c2[i] = permutation[i];
		}
		
		for (int i=0;i<p1;i++){
			int n1, n2;
			n1 = permutation[i];
			n2 = perm2[i];
			if (!is_in_array(c1, n1)) c1[i] = n1;
			if (!is_in_array(c2, n2)) c2[i] = n2;
						 
		}
		
		for (int i=p2;i<nGenes;i++){
			int n1, n2;
			n1 = permutation[i];
			n2 = perm2[i];
			if (!is_in_array(c1, n1)) c1[i] = n1;
			if (!is_in_array(c2, n2)) c2[i] = n2;
		}
		int i=0,j=0;
		
		while (i<nGenes){
			if (c1[i] == -1){
				while (j<nGenes && c2[j] != -1) j++;
				c1[i] = perm2[j];
				c2[j] = permutation[i];			
			}
			i++;
		}
		
		this.setPermutation(c1);
		c.setPermutation(c2);
	}

	/**
	 * Crossover Method : Order [OX] (Deterministic)<br>
	 * 
	 * @param c Second parent
	 */
	private void cross_OX(PermutationChromosome c, int p1, int p2) {
		
		if (p2 < p1){ int tmp = p2; p2 = p1; p1 = tmp; }
		
		int c1[] = new int[nGenes];
		int c2[] = new int[nGenes];
		int[] perm2 = c.getPermutation();
		
		for (int i=0;i<nGenes;i++){
			c1[i] = -1;
			c2[i] = -1;
		}
		
		for (int i=p1;i<p2;i++){
			c1[i] = perm2[i];
			c2[i] = permutation[i];
		}
		
		
		ArrayList<Integer> rest = new ArrayList<>();		
		int pos_c1 = p2, pos_c2 = p2;
		
		for (int i=p2;i<nGenes;i++) rest.add(permutation[i]);
		for (int i=0;i<p1;i++) 		rest.add(permutation[i]);
		for (int i=p2;i<nGenes;i++) rest.add(perm2[i]);
		for (int i=0;i<p1;i++) 		rest.add(perm2[i]);
				
		
		for (Integer n : rest){
			if (!is_in_array(c1, n) && pos_c1%nGenes != p1){
				c1[pos_c1%nGenes] = n;
				pos_c1++;
			}
		}
		
		rest.clear();
		
		for (int i=p2;i<nGenes;i++) rest.add(perm2[i]);
		for (int i=0;i<p1;i++) 		rest.add(perm2[i]);
		for (int i=p2;i<nGenes;i++) rest.add(permutation[i]);
		for (int i=0;i<p1;i++) 		rest.add(permutation[i]);
		
				
		for (Integer n : rest){
			if (!is_in_array(c2, n) && pos_c2%nGenes != p1){
				c2[pos_c2%nGenes] = n;
				pos_c2++;
			}
		}
				
		this.setPermutation(c1);
		c.setPermutation(c2);
	}

	/**
	 * Crossover Method : Order with priority positions [OX_h_pos] (Random)
	 * @param c Second parent
	 */
	private void cross_OX_pos_priority(PermutationChromosome c) {
		Random r = new Random();
		
		int c1[] = new int[nGenes];
		int c2[] = new int[nGenes];
		int[] perm2 = c.getPermutation();

		for (int i=0;i<nGenes;i++){
			c1[i] = -1;
			c2[i] = -1;
		}
		
		for (int i=0;i<nGenes;i++){
			if (r.nextBoolean()){
				c1[i] = (int) perm2[i];
				c2[i] = (int) permutation[i];
			} 
		}
		
		ArrayList<Integer> rest1 = new ArrayList<>();
		for (int i=0;i<nGenes;i++) if (c1[i] == -1) rest1.add(permutation[i]);
		for (int i=0;i<nGenes;i++) if (c2[i] == -1) rest1.add(perm2[i]);
				
		ArrayList<Integer> rest2 = new ArrayList<>();
		for (int i=0;i<nGenes;i++) if (c2[i] == -1) rest2.add(perm2[i]);
		for (int i=0;i<nGenes;i++) if (c1[i] == -1) rest2.add(permutation[i]);	
		
		for (int i=0;i<nGenes;i++){
			while (c1[i] == -1){
				if (!is_in_array(c1, rest1.get(0))){
					c1[i] = rest1.get(0);
				}
				rest1.remove(0);
			}
		}							
				
		for (int i=0;i<nGenes;i++){
			while (c2[i] == -1){
				if (!is_in_array(c2, rest2.get(0))){
					c2[i] = rest2.get(0);
				}
				rest2.remove(0);
			}
		}
		
		this.setPermutation(c1);
		c.setPermutation(c2);
	}

	/**
	 * Crossover Method : Order with priority order [OX_h_ord] (Deterministic)
	 * @param c Second parent
	 */
	private void cross_OX_ord_priority(PermutationChromosome c, int... pos) {
		Arrays.sort(pos);
		
		int c1[] = new int[nGenes];
		int c2[] = new int[nGenes];
		int[] perm2 = c.getPermutation();
		
		for (int i=0;i<nGenes;i++){
			c1[i] = -1;
			c2[i] = -1;
		}
		
		int[] pos1 = new int[pos.length];
		int[] pos2 = new int[pos.length];
		
		for (int i=0;i<pos.length;i++){
			pos1[i] = pos_in_array(permutation, perm2[pos[i]]);
			pos2[i] = pos_in_array(perm2, permutation[pos[i]]);			
		}
		
		Arrays.sort(pos1);
		Arrays.sort(pos2);
		
		for (int i=0;i<pos.length;i++){
			c1[pos2[i]] = permutation[pos[i]];
			c2[pos1[i]] = perm2[pos[i]];
		}
		
		for (int i=0;i<nGenes;i++){
			if (c1[i] == -1) c1[i] = perm2[i];
			if (c2[i] == -1) c2[i] = permutation[i];
		}
		
		this.setPermutation(c1);
		c.setPermutation(c2);
	}
	
	/**
	 * Crossover Method : Cycles [CX] (Deterministic)<br>
	 * @param c Second parent
	 */
	private void cross_CX(PermutationChromosome c) {
		
		int c1[] = new int[nGenes];
		int c2[] = new int[nGenes];
		int[] perm2 = c.getPermutation();
		
		for (int i=0;i<nGenes;i++){
			c1[i] = -1;
			c2[i] = -1;
		}
		
		int pos = 0;
		c1[pos] = permutation[pos];
		pos = pos_in_array(permutation, perm2[pos]);
		while (pos != 0){
			c1[pos] = permutation[pos];
			pos = pos_in_array(permutation, perm2[pos]);
		}

		c2[pos] = perm2[pos];
		pos = pos_in_array(perm2, permutation[pos]);
		while (pos != 0){
			c2[pos] = perm2[pos];
			pos = pos_in_array(perm2, permutation[pos]);
		}
		
		for (int i=0;i<nGenes;i++){
			if (c1[i] == -1) c1[i] = perm2[i];
			if (c2[i] == -1) c2[i] = permutation[i];
		}
		
		this.setPermutation(c1);
		c.setPermutation(c2);
	}

	
	private void cross_ERX(PermutationChromosome c) {
		
		int[] perm2 = c.getPermutation();
		
		ArrayList<ArrayList<Integer>> routes = new ArrayList<>();
		
		for (int i=0;i<nGenes;i++) routes.add(new ArrayList<Integer>());
		
		for (int i=0;i<nGenes;i++){
			routes.get(permutation[i]).add(permutation[(i-1+nGenes)%nGenes]);
			routes.get(permutation[i]).add(permutation[(i+1+nGenes)%nGenes]);
			routes.get(permutation[i]).add(perm2[(pos_in_array(perm2, permutation[i])-1+nGenes)%nGenes]);
			routes.get(permutation[i]).add(perm2[(pos_in_array(perm2, permutation[i])+1+nGenes)%nGenes]);
		}
				
		removeRepetitions(routes);
				
		cross_ERX(routes, permutation[0]);
		c.cross_ERX(routes, perm2[0]);
		
	}

	private void cross_ERX(ArrayList<ArrayList<Integer>> map, int start) {

		Random r = new Random();
		
		int[] child = new int[nGenes];
		boolean[] appears = new boolean[nGenes];
		
		int i=0;
		
		int elem = start;
		int next;
		
		ArrayList<Integer> neighbors;
		ArrayList<Integer> min_map = new ArrayList<>();
		
		while (i<nGenes){
			child[i++] = elem;
			appears[elem] = true;
			
			removeElem(map, elem);
			
			neighbors = map.get(elem); 
			if (neighbors.size() == 0){
				int k = 0;
				while (k<nGenes && appears[k]) k++;
				next = k;
			} else {
				int min_length = 4;
				for (int j=0;j<neighbors.size();j++){
					if (map.get(neighbors.get(j)).size()< min_length){
						min_map.clear();
						min_length = map.get(neighbors.get(j)).size();
					}
					if (map.get(neighbors.get(j)).size() == min_length){
						min_map.add(neighbors.get(j));
					}
				}
				int pos = 0;
				if (min_map.size() > 1) pos = r.nextInt(neighbors.size());
				next = neighbors.get(pos);
			}
			elem = next;
		}

		setPermutation(child);		
	}
	
	private void removeRepetitions(ArrayList<ArrayList<Integer>> map){
		ArrayList<Integer> newRoute = new ArrayList<>();		
		for (int i=0;i<map.size();i++){
			newRoute = new ArrayList<>();
			for (int j=0;j<map.get(i).size();j++){
				
				if (!newRoute.contains(map.get(i).get(j))) newRoute.add(map.get(i).get(j));
			}
			map.set(i,newRoute);
		}
	}	
	
	private void removeElem(ArrayList<ArrayList<Integer>> map, Integer elem){
		ArrayList<Integer> newRoute = new ArrayList<>();
		boolean[] toRemove = new boolean[map.size()];
		for (int i=0;i<map.size();i++){
			newRoute = new ArrayList<>();
			for (int j=0;j<map.get(i).size();j++){				
				if (map.get(i).get(j) != elem) newRoute.add(map.get(i).get(j));
			}
			map.set(i,newRoute);
			if (newRoute.isEmpty()) toRemove[i] = true;
		}
		//for (int i=map.size()-1;i>=0;i--) if (toRemove[i]) map.remove(i);
	}
	
	/**
	 * Crossover Method : Ordinal (Deterministic)<br>
	 * Codifies both chromosomes with ordinal codification and cross them with classical crossover, 
	 * then decodifies both chromosomes to get back the permutation codification. 
	 * @param c Second parent
	 * @param p Cross point
	 */
	private void cross_Ordinal(PermutationChromosome c, int p) {
		
		int c1[] = new int[nGenes];
		int c2[] = new int[nGenes];
		int[] perm2 = c.getPermutation();
		
		ArrayList<Integer> list1 = new ArrayList<>();
		ArrayList<Integer> list2 = new ArrayList<>();
		
		for (int i=0;i<nGenes;i++){
			list1.add(i);
			list2.add(i);
		}
		for (int i=0;i<nGenes;i++){
			
			c1[i] = list1.indexOf(new Integer(permutation[i]));
			list1.remove(c1[i]);
			
			c2[i] = list2.indexOf(new Integer(perm2[i]));
			list2.remove(c2[i]);
		}
		
		//Classic Crossover on c1,c2
		int tmp;
		for (int i=p;i<nGenes;i++){
			tmp = c1[i];
			c1[i] = c2[i];
			c2[i] = tmp;
		}
		//
		
		for (int i=0;i<nGenes;i++){
			list1.add(i);
			list2.add(i);
		}
		
		for (int i=0;i<nGenes;i++){
			
			permutation[i] = list1.get(c1[i]);
			list1.remove(c1[i]);
			
			perm2[i] = list2.get(c2[i]);
			list2.remove(c2[i]);
		}
		
		this.setPermutation(permutation);
		c.setPermutation(perm2);
	}

	private void cross_mult_insertion(PermutationChromosome c, int p1, int p2) {
		
		int c1[] = getPermutation();
		int c2[] = c.getPermutation();
		
		int n = 3;
		
		int[] pos1 = randomElems(n);
		int[] pos2 = randomElems(n);
						
		for (int i=0;i<n;i++){
			mutation_insertion(c2[pos2[i]], pos2[i]);
			c.mutation_insertion(c1[pos1[i]], pos1[i]);
		}
		
	}

	/**
	 * * Mutation Method: Inversion (Deterministic)<br>
	 * Selects two positions within a chromosome at random and then inverts the elements between
	 * these two positions.
	 * @param p1 Position where inversion begins
	 * @param p2 Position where inversion ends
	 */
	private void mutation_inversion(int p1, int p2){
		
		if (p2 < p1){ int tmp = p2; p2 = p1; p1 = tmp; }
		
		int tmp[] = new int[p2-p1];
		for (int i=0;i<p2-p1;i++) tmp[i] = permutation[p1+i];
		for (int i=0;i<p2-p1;i++) permutation[p1+i] = tmp[p2-p1-1-i];
	}
	
	/**
	 * Mutation Method: Exchange (Deterministic)<br>
	 * Exchange between them the elements at p1, p2 positions
	 * @param p1 Position of element 1
	 * @param p2 Position of element 2
	 */
	private void mutation_exchange(int p1, int p2){
		
		if (p2 < p1){ int tmp = p2; p2 = p1; p1 = tmp; }
		
		int tmp = permutation[p1];
		permutation[p1] = permutation[p2];
		permutation[p2] = tmp;
		
	}
	
	/**
	 * Mutation Method: Insertion (Random)<br>
	 * It took n elements and n positios randomly and calls insertion deterministic method
	 * @param n Number of elements to insert
	 */
	private void mutation_insertion(int n){
		
		Random r = new Random();
		for (int i=0;i<n;i++) mutation_insertion(r.nextInt(nGenes), r.nextInt(nGenes));
		
	}	
	
	/**
	 * Mutation Method: Insertion (Deterministic)<br>
	 * Selects the element elem and inserts it at pos position <br>
	 * @param elem Element to insert
	 * @param pos Position on will be inserted the element
	 */
	private void mutation_insertion(int elem, int pos){
		
		//Checking arguments
		if (elem >= nGenes){
			System.err.println("[PermutationChromosome] Mutation - Insertion : Element "+elem+" doesn't belong to permutation");
			return;
		}
		if (pos >= nGenes){
			System.err.println("[PermutationChromosome] Mutation - Insertion : Position "+pos+" doesn't exists on permutation");
			return;
		}
			
		//Processing elements
		int tmp = -1;
		int pos_elem = -1;
		for (int i=0;i<nGenes;i++){
			if (permutation[i] == elem){
				tmp = permutation[i];
				pos_elem = i;
			}
		}
		if (pos_elem > pos){
			for (int i=pos_elem;i>pos;i--) permutation[i] = permutation[i-1];
		} else {
			for (int i=pos_elem;i<pos;i++) permutation[i] = permutation[i+1];
		}
		permutation[pos] = tmp;
		
		setPermutation(permutation);
	}
	
	/**
	 * Mutation Method: Heuristic (Deterministic)<br>
	 * Try all combinations with positions in pos and chooses the best one <br>
	 * @param pos Positions 
	 */
	private void mutation_heuristic(int... pos){
		//Checking arguments
		boolean appears[] = new boolean[nGenes];
		for (int i : pos){
			if (i >= nGenes){
				System.err.println("[PermutationChromosome] Mutation - Heuristic : Element "+i+" doesn't belong to permutation");
				return;
			}
			if (appears[i]){
				System.err.println("[PermutationChromosome] Mutation - Heuristic : Element "+i+" is repeated");
			}
			appears[i] = true;
		}
		
		//Processing elements
		int[] elements = new int[pos.length];
		for (int i=0;i<pos.length;i++) elements[i] = permutation[pos[i]];
		ArrayList<int[]> posibilities = generatePermutations(elements);
		int min_fit = Integer.MAX_VALUE, curr_fit = 0;
		int[] best_perm = permutation.clone();
		for (int[] p : posibilities){
			for (int i=0;i<pos.length;i++) permutation[pos[i]] = p[i]; 
			setPermutation(permutation);
			curr_fit = (int) evaluate();
			if (curr_fit < min_fit){
				min_fit = curr_fit;
				best_perm = permutation.clone();
			}
		}
		setPermutation(best_perm);
		
	}
	
	/**
	 * Mutation Method: Shuffle (Deterministic) <br>
	 * Shuffle elements of permutation between them placing the first half on even positions and
	 * the second one on odd positions
	 */
	private void mutation_shuffle(){
		
		int[] newPermutation = new int[nGenes];
		
		for (int i=0;i<nGenes;i++){
			if (i%2==0){
				newPermutation[i] = permutation[i/2];
			} else {
				newPermutation[i] = permutation[(i+nGenes)/2];
			}
		}
		
		setPermutation(newPermutation);
	}
	
	/**
	 * Mutation Method: Barrel Shifter (Deterministic)<br>
	 * Displace elements offset positions to the left
	 * @param offset Number of positions to displace
	 */
	private void mutation_barrel_shifter(int offset){
		int[] newPermutation = new int[nGenes];
		
		for (int i=0;i<nGenes;i++) newPermutation[i] = permutation[(i+offset)%nGenes];
		
		setPermutation(newPermutation);
	}
	
	public void setPermutation(int[] perm) {
		for (int i=0;i<nGenes;i++) permutation[i] = perm[i];
	}

	public int[] getPermutation(){ return permutation.clone(); }

	private ArrayList<int[]> generatePermutations(int[] elements) {
		ArrayList<int[]> ret = new ArrayList<int[]>();
		generatePermutation(elements, 0, ret);
	    return ret;
	}

	private void generatePermutation(int[] elements, int pos, ArrayList<int[]> list){
	    if(elements.length - pos == 1)
	        list.add(elements.clone());
	    else
	        for(int i = pos; i < elements.length; i++){
	            swap(elements, pos, i);
	            generatePermutation(elements, pos+1, list);
	            swap(elements, pos, i);
	        }
	}

	private void swap(int[] arr, int pos1, int pos2){
	    int h = arr[pos1];
	    arr[pos1] = arr[pos2];
	    arr[pos2] = h;
	}
	
	public boolean is_in_array(int[] a, int value){
		return pos_in_array(a, value) != -1;
	}
	
	public int pos_in_array(int[] a, int value){
		int find = -1;
		int i = 0;
		while (i<a.length && find == -1){
			if (a[i] == value) find = i;
			i++;
		}
		return find;
	}
	
	public int[] randomElems(int n){
		Random r = new Random();
		
		ArrayList<Integer> ints = new ArrayList<>();
		for (int i=0;i<nGenes;i++) ints.add(i);
		
		//XXX Action in case n is greater than nGenes
		
		int[] rs = new int[n];
		for (int i=0;i<n;i++){
			int pos = r.nextInt(ints.size());
			rs[i] = ints.get(pos);
			ints.remove(pos); 
		}
		
		Arrays.sort(rs);
		return rs;
	}
	
	public boolean is_correct(){
		boolean correct = true;
		boolean mask[] = new boolean[nGenes];
		for (int i=0;i<nGenes;i++) mask[permutation[i]] = true;
		for (boolean b: mask) correct &= b;
		return correct;
	}

	@Override
	public String toString() { return Arrays.toString(permutation) + " -> " + evaluate() ; }

	@Override
	public float evaluate() { return 0; }

	@Override
	public Chromosome getCopy() { return new PermutationChromosome(this); }

	
	@Override
	public boolean equals(Object obj) {
		if (null == obj) return false;
		if (this == obj) return true;
		if (!(obj instanceof PermutationChromosome)) return false;
		PermutationChromosome pc = (PermutationChromosome) obj;
		if (this.nGenes != pc.nGenes) return false;
		boolean eq = true;
		int[] perm2 = pc.getPermutation();
		for (int i=0;i<nGenes;i++) eq &= permutation[i] == perm2[i];		
		return eq;
	}

	public static void main(String[] args){
		PermutationChromosome p1 = new PermutationChromosome(9);
		PermutationChromosome p2 = new PermutationChromosome(9);
		p1.randomInit(0);
		p2.randomInit(0);
		System.out.println(p1); System.out.println(p2);
		p1.cross_ERX(p2);
		System.out.println(p1); System.out.println(p2);
	}
}

